<!DOCTYPE HTML PUBLIC "-//IETF//DTD HTML//EN">
<html>

<head>
<title>SSF.OS.BGP4 Validation</title>
</head>

<body bgcolor="white">

<h2>SSF.OS.BGP4 Validation</h2>

<h3>Methodology</h3>

<p align="justify">
No well-established method currently exists for validating an
implementation of BGP, so we began composing our own validation tests
for SSF.OS.BGP4</a>.  They vary from very simple, strict verifications
of the most basic behaviors of BGP (such as setting up and tearing
down peering sessions) to more macroscopic tests which check the
general characteristics of BGP in larger networks (such as ensuring
that packets sent from one part of a network to another reach their
destination).  The BGP-4 specification <a
href="index.html#ref1">[1]</a> leaves room for an essentially
limitless number of acceptable variations in behavior, making complete
verification a difficult if not impossible task.  Our approach here is
not an attempt to confirm perfect behavior of the implementation, but
simply to reduce the number of possible incorrect behaviors by showing
that it conforms to certain restrictions.  The validation tests which
take the strict and simple approach establish a foundation of basic
functional behaviors upon which the more complex behaviors are built.
The macroscopic tests blur the details of its behavior, essentially
performing a sanity check to ensure that what's getting done at the
network level is what we would expect.  (Whether or not it's getting
done the way that it should be is never guaranteed in this type of
test.)
</p>

<p align="justify">
Together, these two types of validation test give us at least some
assurance that the behavior is reasonable.  Eliminating all
possibility for incorrect behavior is almost certainly a fantasy that
will never be achieved.  However, we can at least make an effort to
narrow it down.
</p>


<h3>Test List</h3>

<table cellpadding="0" cellspacing="0" border="0">

<tr>
<td align="right"><a href="#drop-peer"><code>drop-peer</code></a>:</td>
<td>&nbsp;&nbsp;</td>
<td>Terminating a Peering Session</td>
</tr>

<tr>
<td align="right"><a href="#drop-peer2"><code>drop-peer2</code></a>:</td>
<td>&nbsp;&nbsp;</td>
<td>Routing Updates after Session Termination</td>
</tr>

<tr>
<td align="right"><a href="#keep-peer"><code>keep-peer</code></a>:</td>
<td>&nbsp;&nbsp;</td>
<td>Maintaining a Peering Session</td>
</tr>

<tr>
<td align="right"><a href="#route-distrib"><code>route-distrib</code></a>:</td>
<td>&nbsp;&nbsp;</td>
<td>Route Distribution between Peers</td>
</tr>

<tr>
<td align="right"><a href="#propagation"><code>propagation</code></a>:</td>
<td>&nbsp;&nbsp;</td>
<td>Propagation of Learned Route Information</td>
</tr>

<tr>
<td align="right"><a href="#select"><code>select</code></a>:</td>
<td>&nbsp;&nbsp;</td>
<td>Selecting from Multiple Route Options</td>
</tr>

<tr>
<td align="right"><a href="#withdrawals"><code>withdrawals</code></a>:</td>
<td>&nbsp;&nbsp;</td>
<td>Handling a Withdrawal Update</td>
</tr>

<tr>
<td align="right"><a href="#loopback"><code>loopback</code></a>:</td>
<td>&nbsp;&nbsp;</td>
<td>Using Loopback Addresses</td>
</tr>

<tr>
<td align="right"><a href="#reflection"><code>reflection</code></a>:</td>
<td>&nbsp;&nbsp;</td>
<td>Route Reflection</td>
</tr>

<tr>
<td align="right"><a href="#ibgp"><code>ibgp</code></a>:</td>
<td>&nbsp;&nbsp;</td>
<td>Internal BGP</td>
</tr>

<tr>
<td align="right"><a href="#reconnect"><code>reconnect</code></a>:</td>
<td>&nbsp;&nbsp;</td>
<td>Reconnecting after Session Termination</td>
</tr>

<tr>
<td align="right"><a href="#goodgadget"><code>goodgadget</code></a>:</td>
<td>&nbsp;&nbsp;</td>
<td>Simple Route Filtering</td>
</tr>

<tr>
<td align="right"><a href="#forwarding1"><code>forwarding1</code></a>:</td>
<td>&nbsp;&nbsp;</td>
<td>Forwarding in a Moderately Sized Network</td>
</tr>

<tr>
<td align="right"><a href="#forwarding2"><code>forwarding2</code></a>:</td>
<td>&nbsp;&nbsp;</td>
<td>Forwarding in a Moderately Size, Hierarchically Addressed Network</td>
</tr>

<tr>
<td align="right"><a href="#forwarding3"><code>forwarding3</code></a>:</td>
<td>&nbsp;&nbsp;</td>
<td>Forwarding in a Moderately Sized Network Including IBGP</td>
</tr>

</table>

<h3>General Format</h3>

<p align="justify">
Each test is organized according to the same template.  Each test has
a shorthand name, such as <code>drop-peer</code> or
<code>goodgadget</code>.  Let <code>x</code> be the shorthand name for
any test.  Then <code>x</code> is located in directory
<code>BGP4/test/x/</code> of the distribution.  Within that directory
there are several files.  The DML source file for the model is
<code>x.dml</code>, and <code>x.gif</code> is a graphical image of the
modeled network.  (Additional library DML source files are <a
href="../test/dictionary.dml"><code>BGP4/test/dictionary.dml</code></a>,
which contains commonly used network building blocks, and <a
href="../../../../../examples/net.dml"><code>ssfnet/examples/net.dml</code></a>,
which is a schema for verifying the correctness of SSFNet DML code.)
<code>Makefile</code> contains specifics about running the model,
including the exact command which is used to execute it.  That command
is essentially
</p>

<p>
<code>&nbsp;&nbsp;&nbsp;&nbsp;java&nbsp;SSF.Net.Net&nbsp;&lt;runtime&gt;&nbsp;x.dml&nbsp;../dictionary.dml ../../../../../../examples/net.dml</code>
</p>

<p align="justify">
where <code>&lt;runtime&gt;</code> is the length of the simulation in
seconds.  (In <code>Makefile</code> the length of the simulation is
defined by the <code>RUNTIME</code> variable.)  Some tests require
additional source code.  If that is the case, the code is located in a
directory called <code>BGP4/test/x/src/</code>, and
<code>Makefile</code> will automatically compile it before starting
the simulation.  All output from the simulation is directed to file
<code>test-raw.out</code>.  This file should look very similar to (but
not necessarily exactly the same as) the archived raw output in
<code>x-raw.out</code>.  The file <code>test.out</code> contains only
those lines from <code>test-raw.out</code> which are specifically
intended for validation purposes.  The file <code>x.out</code>
contains the archived validation output.  In order for the validation
test to be successful, <code>test.out</code> must be exactly the same
as <code>x.out</code>.
</p>

<a name="drop-peer">
<h3>Terminating a Peering Session</h3>

<p>
Files specific to this test are located in <a
href="../test/drop-peer/">BGP4/test/drop-peer/</a>.
</p>

<p align="justify">
This test checks the behavior of a BGP speaker when one of its peers
is non-responsive.
</p>

<p align="justify">
In this test, a BGP speaker establishes a peering session with a
neighbor that is henceforth non-responsive.  The test is successful if
the BGP speaker eventually sends a Notification message to this peer
(when the Hold Timer for that peer expires).
</p>
	
<a name="drop-peer2">
<h3>Routing Updates after Session Termination</h3>

<p>
Files specific to this test are located in <a
href="../test/drop-peer2/">BGP4/test/drop-peer2/</a>.
</p>

<p align="justify">
This test checks the behavior of a BGP speaker after a peering session
is terminated.
</p>

<p align="justify">
In this test, a BGP speaker establishes two peers, but then the
session with one of them is broken.  The test is successful if the BGP
speaker sends an update to its remaining peer in order to withdraw the
former route to the disconnected peer.
</p>
	
<a name="keep-peer">
<h3>Maintaining a Peering Session</h3>

<p>
Files specific to this test are located in <a
href="../test/keep-peer/">BGP4/test/keep-peer/</a>.
</p>

<p align="justify">
This test checks the mechanisms used to keep an existing peering
session intact.
</p>

<p align="justify">
In this test, a BGP speaker establishes a peering session with a
neighboring BGP speaker.  The test is successful if, after an
arbitrary amount of time, the peering session still exists.
</p>

<a name="route-distrib">
<h3>Route Distribution between Peers</h3>

<p>
Files specific to this test are located in <a
href="../test/route-distrib/">BGP4/test/route-distrib/</a>.
</p>

<p align="justify">
This test checks to make sure that a router receives routing
information advertised by a peer.
</p>

<p align="justify">
In this test, a BGP speaker has a single peer.  Routing information
for the BGP speaker's AS is advertised to that peer.  The test is
successful if the peer correctly adds an entry in its local forwarding
table for this routing information.
</p>

<a name="propagation">
<h3>Propagation of Learned Route Information</h3>

<p>
Files specific to this test are located in <a
href="../test/propagation/">BGP4/test/propagation/</a>.
</p>

<p align="justify">
This test checks that a BGP speaker correctly propagates learned
routes to other BGP speakers who may not know of these routes yet.
</p>

<p align="justify">
In this test, there are three ASes connected in a line. (AS X connects
to AS Y, and AS Y connects to AS Z.)  The test is successful if a
route advertised by AS X is propagated through AS Y to AS Z and
inserted into the forwarding table at AS Z.
</p>

<a name="select">
<h3>Selecting from Multiple Route Options</h3>

<p>
Files specific to this test are located in <a
href="../test/select/">BGP4/test/select/</a>.
</p>

<p align="justify">
This test checks that a BGP speaker chooses routes properly when there
is more than one option for forwarding to a particular destination.
</p>

<p align="justify">
In this test, there are three ASes--X, Y and Z--each with one BGP
router.  Each of these BGP routers has the other two as neighbors.
The BGP speaker at AS X advertises routing information about its AS
(AS X) to both Y and Z.  Y in turn forwards the routing information to
Z (and likewise Z also forwards it to Y).  Z's policy is to choose
routes with the shortest number of hops through other ASes.  The test
is successful if, after having received the advertisement about X both
from X and Y, Z chooses the direct (1-hop) route to X and installs it
in the forwarding table at the local router.
</p>

<a name="withdrawals">
<h3>Handling a Withdrawal Update</h3>

<p>
Files specific to this test are located in <a
href="../test/withdrawals/">BGP4/test/withdrawals/</a>.
</p>

<p align="justify">
This test checks that a BGP speaker handles the withdrawal of routing
information correctly by removing the route from the local forwarding
table.
</p>

<p align="justify">
In this test, one BGP speaker advertises a bogus route to a peer,
waits a little while, and then sends a withdrawal for that route.  The
test is successful if the peer receives the advertisement, adds the
route to the local routing table, and later receives the withdrawal
and correctly removes the route from the routing table.
</p>

<a name="loopback">
<h3>Using Loopback Addresses</h3>

<p>
Files specific to this test are located in <a
href="../test/loopback/">BGP4/test/loopback/</a>.
</p>

<p align="justify">
This test checks the use of loopback (virtual) interfaces as
destination addresses for Internal BGP connections.
</p>

<p align="justify">
The network in this test is composed of two ASes, AS1 and AS2.  AS1
has only a single router, 1:1.  AS2 has three routers--2:1, 2:2, and
2:3--with one link from 2:1 to 2:2 and another link from 2:2 to 2:3.
There is one inter-AS link from 1:1 to 2:1.  BGP is running at all of
these routers, and there is a full mesh of IBGP peering sessions
between the three routers in AS2.  Note that this is in spite of the
fact that there are not physical point-to-point links between each
pair of routers--2:1 and 2:3 are not directly connected.  Each router,
in addition to having physical interfaces, also has one virtual, or
loopback, interface.  All of the Internal BGP peering sessions use
loopback addresses for peer destination addresses.  This test is to
check that peering sessions are properly established when using
loopback addresses rather than physical interface addresses.
Furthermore, it tests that multihop peering sessions also work
correctly.  The test is successful if 2:3 receives an advertisement
for a route to AS1.
</p>

<a name="reconnect">
<h3>Reconnecting after Session Termination</h3>

<p>
Files specific to this test are located in <a
href="../test/reconnect/">BGP4/test/reconnect/</a>.
</p>

<p align="justify">
This test checks the ability of a BGP speaker to reestablish a peering
session with a former peer.
</p>

<p align="justify">
In this test, a BGP speaker establishes two peers, but then the
session with one of them is broken.  The two BGP speakers that got
disconnected then attempt to reestablish a session.  The test is
successful if the third speaker receives two separate updates which
both advertise the same route to the speaker which was disconnected.
(There will have been a withdrawal for that route in between the two
advertisements.)
</p>

<a name="ibgp">
<h3>Internal BGP</h3>

<p>
Files specific to this test are located in <a
href="../test/ibgp/">BGP4/test/ibgp/</a>.
</p>

<p align="justify">
This test checks that a BGP speaker correctly forwards updates to its
Internal BGP peers.
</p>

<p align="justify">
In this test, there are three ASes connected in a line.  AS X
connects to AS Y and AS Y connects to AS Z.  AS Y, the middle AS, has
two BGP routers, while the other two have only one BGP router.  The
test is successful if AS Z receives an update message advertising a
route to AS X.  This would imply that Internal BGP worked properly
within AS Y.
</p>

<a name="reflection">
<h3>Route Reflection</h3>

<p>
Files specific to this test are located in <a
href="../test/reflection/">BGP4/test/reflection/</a>.
</p>

<p align="justify">
This test checks the behavior of (Internal BGP) route reflectors.
</p>

<p align="justify">
In this test there are four ASes (see the image file <a
href="../test/reflection/reflection.gif">reflection.gif</a>).  The AS
that is focussed upon (AS M) contains six routers and three reflection
clusters (one of them has only a single reflector with no clients).
The other three ASes (X, Y and Z) contain only one router apiece, and
each attach in one place to the primary AS.  The test traces the
advertisement of route information injected at one of the auxiliary
ASes (X) throughout the entire network.  The test is successful if the
route information is reflected three times by router RR1 and once by
RR2, and if each BGP router in the network receives exactly one update
message containing this route information.
</p>

<a name="goodgadget">
<h3>Simple Route Filtering</h3>

<p>
Files specific to this test are located in <a
href="../test/goodgadget/">BGP4/test/goodgadget/</a>.
</p>

<p align="justify">
This test checks the behavior of BGP speakers which filter based on
the AS path attribute.
</p>

<p align="justify">
In this test there are four ASes (see the image file <a
href="../test/goodgadget/goodgadget.gif">goodgadget.gif</a>).  The
three points of the triangle (AS1, AS2, and AS3) are all configured to
give the direct path to AS0 low priority.  AS1 and AS2 do not accept
counter-clockwise paths (they deny routes advertising those paths) and
thus prefer the clockwise paths.  AS3 has no preference between
clockwise and counterclockwise paths.  The test is successful if the
local routing information at the routers in AS1, AS2, and AS3 for the
path to AS0 is as follows.  The router in AS1 must indicate that it
has chosen the path [AS3 AS0].  The router in AS2 must indicate that
it has chosen the path [AS2 AS3 AS0].  Finally, the router in AS3 must
indicate that it has chosen the path [AS1 AS2 AS3 AS0].
</p>

<p>
Thanks to Tim Griffin for contributing this test network. Refer to the SIGCOMM
1999 paper <i>An Analysis of BGP Convergence Properties</i> (Griffin and
Wilfong) for similar examples of network "gadgets" like this one.
</p>

<a name="forwarding1">
<h3>Forwarding in a Moderately Sized Network</h3>

<p>
Files specific to this test are located in <a
href="../test/forwarding1/">BGP4/test/forwarding1/</a>.
</p>

<p align="justify">
This test does not examine a specific aspect of BGP, but is a more
general test of BGP's operation on a macroscopic level.  It checks
that traffic in a network of 32 autonomous systems is being correctly
forwarded from source to destination.
</p>

<p align="justify">
In this test, there is a network of 32 autonomous systems, each with
one router running BGP and one host.  At each host, there is an
application running which sends one packet to each of the other 31
hosts in the network.  The test is successful if all
<code>31*32=992</code> messages are received by the correct hosts.
</p>

<a name="forwarding2">
<h3>Forwarding in a Moderately Sized, Hierarchically Addressed Network</h3>

<p>
Files specific to this test are located in <a
href="../test/forwarding2/">BGP4/test/forwarding2/</a>.
</p>

<p align="justify">
This test does not examine a specific aspect of BGP, but is a more
general test of BGP's operation on a macroscopic level.  It checks
that traffic in a hierarchically addressed network of 32 autonomous
systems is being correctly forwarded from source to destination.
</p>

<p align="justify">
In this test, there is a network of 32 autonomous systems, each with
one router running BGP and one host.  At each host, there is an
application session running which sends one packet to each of the
other 31 hosts in the network.  The test is successful if all
<code>31*32=992</code> messages are received by the correct hosts.
</p>

<a name="forwarding3">
<h3>Forwarding in a Moderately Sized Network Including IBGP</h3>

<p>
Files specific to this test are located in <a
href="../test/forwarding3/">BGP4/test/forwarding3/</a>.
</p>

<p align="justify">
This test does not examine a specific aspect of BGP, but is a more
general test of BGP's operation on a macroscopic level.  It checks
that traffic in a network of 31 autonomous systems is being correctly
forwarded from source to destination.  The network is hierarchically
addressed and utilizes Internal BGP.
</p>

<p align="justify">
In this test, there is a network of 31 autonomous systems, each with a
varying number of routers running BGP.  For each router in an AS,
there is one host connected to it.  There are a total of 90 routers
and 90 hosts.  At each host, there is an application session running
which sends one packet to every other host in the network.  The test
is successful if all <code>90*89=8010</code> messages are received by
the correct hosts.
</p>


<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>
<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>
<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>
<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>


</body>
</html>
